package Leetcode;

import java.util.*;

/**
 * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 */
public class 力扣15_三数之和 {

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeSum(nums);
        System.out.println(lists);
    }

    // 过滤重复数据
    static Set<String> set = new HashSet<>();

    // 优化三层循环 首先排序 确定第一个数字 然后 对后面的所有数字收尾一次确定两个 再根据结果确定下次运行
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int num = nums[i] + nums[j] + nums[k];
                if (num == 0) {
                    List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                    if (set.add(list.toString())) {
                        result.add(list);
                    }
                    k--;
                }
                if (num < 0) {
                    j++;
                }
                if (num > 0) {
                    k--;
                }
            }
        }
        return result;
    }

    public static List<List<Integer>> threeSum2(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        threeSum(nums, result, 0, new LinkedList<>());
        return result;
    }

    /**
     * 递归回溯算法
     */
    public static void threeSum(int[] nums, List<List<Integer>> result, int index, LinkedList<Integer> numList) {
        // 1 终止条件 数字到达3个
        if (numList.size() == 3) {
            int sum = 0;
            for (Integer num : numList) {
                sum += num;
            }
            if (sum == 0) {
                boolean add = set.add(numList.toString());
                if (add) {
                    result.add(new ArrayList<>(numList));
                }
            }
            return;
        }
        // 每次往后取数字 避免重复
        for (int i = index; i < nums.length; i++) {
            // 2 剪枝 如果这个下标已有 或者这个数字已经存在了 就跳过
            numList.addLast(nums[i]);
            threeSum(nums, result, i + 1, numList);
            // 3 回溯 给下次循环让位
            numList.removeLast();
        }
    }

    // 暴力三层循环
    public static List<List<Integer>> threeSum3(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                        if (set.add(list.toString())) {
                            result.add(list);
                        }
                    }
                }
            }
        }
        return result;
    }

}
